package 面试经典150题.二叉树;

import common.TreeNode;

/**
 * @author tmh
 * @date 2024/6/24 22:20
 * @description
 */
public class T236二叉树的最近公共祖先 {
    //https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-interview-150
    //这个链接的思路讲的很不错
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //分类讨论，如果当前节点是空结点，当前节点是p,当前节点是q，那么就直接返回当前节点
        if(root==null || root==p||root==q){
            return root;
        }
        //往左遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //往右遍历
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //如果左为空，那么就返回右子树的结果right
        if(left==null){
            return right;
        }
        //如果右为空，那么就返回左子树的结果
        if(right==null){
            return left;
        }
        //如果左右子树都为空的话，那么就直接返回当前节点
        return root;
    }

    }
